package week_six;

public class CoinChange_322 {

    private int INF;

    public int coinChange(int[] coins, int amount) {
        //DP
        //状态 dp[i],amount=i时最少钱币数
        //状态转移 dp[i] = min {dp[i-coin] + 1}
        //边界 dp[0]=0, dp[i]=INF, 最差情况
        int[] dp = new int[amount + 1];
        INF = (int) 1e9;
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            dp[i] = INF;
            for (int j = 0; j < coins.length; j++) {
                if (i - coins[j] >= 0) {
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                    // System.out.println(i+" : "+dp[i]);
                }
            }
        }
        if (dp[amount] < INF) {
            return dp[amount];
        } else return -1;

    }

    public int coinChange1(int[] coins, int amount) {
        //dfs,记忆化搜索
        INF = (int) 1e9;
        int[] res = new int[amount + 1];
        int ans = calc(coins, amount, res);
        if (ans < INF) return ans;
        else return -1;
    }

    private int calc(int[] coins, int amount, int[] res) {
        if (amount == 0) return 0;
        if (amount < 0) return INF;
        if (res[amount] != 0) return res[amount];
        res[amount] = INF;
        for (int coin : coins) {
            res[amount] = Math.min(res[amount], calc(coins, amount - coin, res) + 1);
            // System.out.println(amount +" updated "+res[amount]);
        }
        return res[amount];
    }
}
